import java.util.*;

/**
 * Created by L.jp
 * Description:请根据二叉树的前序遍历，中序遍历恢复二叉树，并打印出二叉树的右视图
 * 要求： 空间复杂度 O(n)，时间复杂度 O(n)
 * User: 86189
 * Date: 2022-06-30
 * Time: 11:56
 */
class TreeNode{
    int val;
    TreeNode left=null;
    TreeNode right=null;
    public TreeNode(int val){
        this.val = val;
    }
    public TreeNode(TreeNode left,TreeNode right){
        this.left=left;
        this.right = right;
    }
}
//1.重建二叉树
//2.利用层序遍历，借助队列找到每一层的最后一个节点，把这些节点加入一个数组即可
public class Solution {
    //重建二叉树
    public TreeNode reBuild(int[] pre,int[] vin){
        int n=pre.length;
        int m=vin.length;
        if(n==0 || m==0){
            return null;
        }
        //先确定根节点
        TreeNode root=new TreeNode( pre[0] );
        //再在中序遍历数组里找到根节点的位置，划分左右子树数组，然后再确定节点
        for(int i = 0; i < m; i++){
            //利用Arrays.copyOfRange函数实现左右子树数组的分割，他返回的是一个新的数组作为参数
            if(pre[0]==vin[i]){
                root.left=reBuild( Arrays.copyOfRange( pre,1,i+1 ),
                                   Arrays.copyOfRange( vin,0,i ));
                root.right = reBuild(Arrays.copyOfRange(pre, i+1, pre.length),
                                     Arrays.copyOfRange( vin,i+1,vin.length ));
                break;
            }
        }
        return root;
    }
    //存储二叉数的右视图
    public List<Integer> getRightView(TreeNode root){
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        List<Integer> ret=new ArrayList<>();
        queue.add( root );
        while ( !queue.isEmpty() ){
            //弹出每一层的节点，直到队列的大小为0时，此时弹出的节点就是最右边的节点
            //此时队列的大小就是二叉树每一层的节点个数
            int size=queue.size();
            TreeNode cur=null;
            for(int i=size;i>0;i--){
                cur=queue.poll();
                if(cur.left!=null){
                    queue.add( cur.left );
                }
                if(cur.right!=null){
                    queue.add(cur.right);
                }
            }
            //此时弹出节点直到队列的大小为0了，那么最后一个弹出的节点就是每一层右边的节点
            ret.add( cur.val );
        }
        return ret;
        
    }
    public int[] solve (int[] xianxu, int[] zhongxu) {
        //构建二叉树
        TreeNode root=reBuild( xianxu,zhongxu );
        List<Integer> list=getRightView( root );
        int[] ret=new int[list.size()];
        for(int i = 0; i <list.size(); i++){
            ret[i]=list.get(i);
        }
        return ret;
    }
}
